import java.util.ArrayList;

import info.gridworld.grid.AbstractGrid;
import info.gridworld.grid.Location;


/**
 * An <code>UnboundedGrid2</code> is a rectangular grid with an unbounded number of rows and
 * columns. <br />
 * The implementation of this class is testable on the AP CS AB exam.
 */
public class UnboundedGrid2<E> extends AbstractGrid<E>
{
	private Object[][] occ;
	private int d;

    /**
     * Constructs an empty unbounded grid.
     */
    public UnboundedGrid2()
    {
        d = 16;
        occ = new Object[d][d];
    }

    public int getNumRows()
    {
        return -1;
    }

    public int getNumCols()
    {
        return -1;
    }

    public boolean isValid(Location loc)
    {
        return loc.getCol() >= 0 && loc.getRow() >= 0;
    }

    public ArrayList<Location> getOccupiedLocations()
    {
        ArrayList<Location> a = new ArrayList<Location>();
        for (int i = 0; i < d; i++)
        {
        	for (int j = 0; j < d; j++)
        	{
        		Location loc = new Location(i,j);
        		if (get(loc) != null)
        		{
        			a.add(loc);
        		}
        	}
        }
        return a;
    }

    @SuppressWarnings("unchecked")
	public E get(Location loc)
    {
        if (!isValid(loc))
            throw new NullPointerException("loc is not valid");
        if (loc.getCol() >= d || loc.getRow() >= d)
        {
        	return null;
        }
        return (E) occ[loc.getRow()][loc.getCol()];
    }

    public E put(Location loc, E obj)
    {
    	if (!isValid(loc))
            throw new NullPointerException("loc is not valid");
        if (obj == null)
            throw new NullPointerException("obj == null");
        if (loc.getRow() >= d || loc.getCol() >= d)
        {
        	resize(loc);
        }
        E oldocc = get(loc);
        occ[loc.getRow()][loc.getCol()] = obj;
        return oldocc;
    }

    public E remove(Location loc)
    {
    	if (!isValid(loc))
            throw new NullPointerException("loc is not valid");
    	if (loc.getRow() >= d || loc.getCol() >= d)
        {
        	return null;
        }
    	E oldocc = get(loc);
    	occ[loc.getRow()][loc.getCol()] =null;
        return oldocc;
    }
    /**
     * resize the grid according to the location
     * @param loc
     */
    private void resize(Location loc)
    {
    	int cur_d = d;
    	while (loc.getCol() >= cur_d || loc.getRow() >= cur_d)
    	{
    		cur_d *= 2;
    	}
    	Object[][] t = new Object[cur_d][cur_d];
    	for (int i = 0; i < d; i++)
    	{
    		for (int j = 0; j < d; j++)
    		{
    			t[i][j] = occ[i][j];
    		}
    	}
    	occ = t;
    	d = cur_d;
    }
}
